package pers.vic.basics.leetcode;

import java.util.Stack;

/**
 * @author Vic.xu
 * @description:20. 有效的括号
 * @date: 2020/11/11 10:08
 */
public class J0020_E_IsValid {
    /*
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    注意空字符串可被认为是有效字符串。
    输入: "()"  输出: true
   输入: "()[]{}" 输出: true

     */

    /**
     * 遍历每个字符
     * 遇到左边的括号类型就入栈
     * 遇到右边的括号 就去栈里匹配
     */
    public static boolean isValid(String s) {
        if (s == null || s.isEmpty()) {
            return true;

        }
        Stack<Character> stack = new Stack<>();
        char[] cs = s.toCharArray();
        for (char c : cs) {
            switch (c) {
                case '{':
                case '[':
                case '(':
                    stack.push(c);
                    break;
                case '}':
                case ']':
                case ')':
                    if (stack.isEmpty()) {
                        return false;
                    }
                    char pop = stack.pop();

                    boolean match = (c == '}' && pop == '{') || (c == ']' && pop == '[') || (c == ')' && pop == '(');
                    if (!match) {
                        return false;
                    }
                    break;
                default:
                    break;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        /*
        System.out.println(isValid("()"));
        System.out.println(isValid("()[]{}"));
        System.out.println(isValid("(]"));
        System.out.println(isValid("([)]"));
        System.out.println(isValid("{[]}"));
        System.out.println(isValid("["));
        */
        System.out.println(isValid("()[]{}"));
    }

}
